package algocasts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P112_CombinationSum {
    private void combSum(int[] nums, int target, int start,
                         List<Integer> elem, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(elem));
        }
        if (target < 0) return;
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) break;
            elem.add(nums[i]);
            combSum(nums, target - nums[i], i, elem, result);
            elem.remove(elem.size() - 1);
        }
    }

    // Time :O(n^(target/min)), Space:O(target/min)
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> elem = new ArrayList<>();
        Arrays.sort(candidates);
        combSum(candidates, target, 0, elem, result);
        return result;
    }
}
